home *** CD-ROM | disk | FTP | other *** search
/ Mac Power 1997 December / MACPOWER-1997-12.ISO.7z / MACPOWER-1997-12.ISO / AMUG / PROGRAMMING / Raven 1.2.sit / Raven 1.2 / • Extras • / SGI STL / tree.h < prev    next >
C/C++ Source or Header  |  1997-05-28  |  41KB  |  1,228 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1996
  4.  * Silicon Graphics Computer Systems, Inc.
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Silicon Graphics makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  *
  15.  * Copyright (c) 1994
  16.  * Hewlett-Packard Company
  17.  *
  18.  * Permission to use, copy, modify, distribute and sell this software
  19.  * and its documentation for any purpose is hereby granted without fee,
  20.  * provided that the above copyright notice appear in all copies and
  21.  * that both that copyright notice and this permission notice appear
  22.  * in supporting documentation.  Hewlett-Packard Company makes no
  23.  * representations about the suitability of this software for any
  24.  * purpose.  It is provided "as is" without express or implied warranty.
  25.  *
  26.  * Exception Handling:
  27.  * Copyright (c) 1997
  28.  * Mark of the Unicorn, Inc.
  29.  *
  30.  * Permission to use, copy, modify, distribute and sell this software
  31.  * and its documentation for any purpose is hereby granted without fee,
  32.  * provided that the above copyright notice appear in all copies and
  33.  * that both that copyright notice and this permission notice appear
  34.  * in supporting documentation.  Mark of the Unicorn makes no
  35.  * representations about the suitability of this software for any
  36.  * purpose.  It is provided "as is" without express or implied warranty.
  37.  *
  38.  * Adaptation:
  39.  * Copyright (c) 1997
  40.  * Moscow Center for SPARC Technology
  41.  *
  42.  * Permission to use, copy, modify, distribute and sell this software
  43.  * and its documentation for any purpose is hereby granted without fee,
  44.  * provided that the above copyright notice appear in all copies and
  45.  * that both that copyright notice and this permission notice appear
  46.  * in supporting documentation.  Moscow Center for SPARC Technology makes no
  47.  * representations about the suitability of this software for any
  48.  * purpose.  It is provided "as is" without express or implied warranty.
  49.  *
  50.  */
  51.  
  52.  
  53. #ifndef __SGI_STL_TREE_H
  54. #define __SGI_STL_TREE_H
  55.  
  56. /*
  57.  
  58. Red-black tree class, designed for use in implementing STL
  59. associative containers (set, multiset, map, and multimap). The
  60. insertion and deletion algorithms are based on those in Cormen,
  61. Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
  62. except that
  63.  
  64. (1) the header cell is maintained with links not only to the root
  65. but also to the leftmost node of the tree, to enable constant time
  66. begin(), and to the rightmost node of the tree, to enable linear time
  67. performance when used with the generic set algorithms (set_union,
  68. etc.);
  69.  
  70. (2) when a node being deleted has two children its successor node is
  71. relinked into its place, rather than copied, so that the only
  72. iterators invalidated are those referring to the deleted node.
  73.  
  74. */
  75.  
  76. #include <stddef.h>
  77. # ifndef __SGI_STL_ALGOBASE_H
  78. #  include <algobase.h>
  79. # endif
  80. # ifndef __SGI_STL_ITERATOR_H
  81. #  include <iterator.h>
  82. # endif
  83. # ifndef __SGI_STL_ALLOC_H
  84. #  include <alloc.h>
  85. # endif
  86.  
  87. # if defined ( __STL_USE_ABBREVS )
  88. // ugliness is intentional - to reduce conflicts possibility
  89. #  define __rb_tree_node_base       _rbT__NB
  90. #  define __rb_tree_node            _rbT__N
  91. #  define __rb_tree_base_iterator   _rbTB__It
  92. #  define __rb_tree_iterator        _rbT__It
  93. #  define __rb_tree_const_iterator  _rbT__cIt
  94. #  define __rb_tree_base            _rbT__B
  95. # endif
  96.  
  97. __BEGIN_STL_NAMESPACE
  98.  
  99. typedef bool __rb_tree_color_type;
  100. const __rb_tree_color_type __rb_tree_red = false;
  101. const __rb_tree_color_type __rb_tree_black = true;
  102.  
  103. struct __rb_tree_node_base
  104. {
  105.   typedef __rb_tree_color_type color_type;
  106.   typedef __rb_tree_node_base* base_ptr;
  107.  
  108.   color_type color; 
  109.   base_ptr parent;
  110.   base_ptr left;
  111.   base_ptr right;
  112.  
  113.   static base_ptr minimum(base_ptr x)
  114.   {
  115.     while (x->left != 0) x = x->left;
  116.     return x;
  117.   }
  118.  
  119.   static base_ptr maximum(base_ptr x)
  120.   {
  121.     while (x->right != 0) x = x->right;
  122.     return x;
  123.   }
  124. };
  125.  
  126. template <class Value>
  127. struct __rb_tree_node : public __rb_tree_node_base
  128. {
  129.   Value value_field;
  130. };
  131.  
  132.  
  133. struct __rb_tree_base_iterator
  134. # if defined ( __STL_DEBUG )
  135.     : public __safe_base 
  136. # endif
  137. {
  138.   typedef __rb_tree_node_base::base_ptr base_ptr;
  139.   typedef ptrdiff_t distance_type;
  140.   base_ptr node;
  141. # if defined ( __STL_DEBUG )
  142.   base_ptr get_iterator() const { return node; }  
  143.   base_ptr owner() const {
  144.       const __safe_base* ptr = __safe_base::owner();
  145.       return ptr ? base_ptr(ptr->owner_) : base_ptr(0); 
  146.   }
  147.   __rb_tree_base_iterator() : __safe_base(0) {}
  148.   __rb_tree_base_iterator(const __safe_base* root, base_ptr p) : 
  149.       __safe_base(root), node(p) {}
  150. # endif
  151.   void increment()
  152.   {
  153.     __stl_verbose_assert(valid(), __STL_MSG_INVALID_ITERATOR); 
  154.     __stl_verbose_assert(node!=owner(), __STL_MSG_INVALID_ADVANCE); 
  155.     if (node->right != 0) {
  156.       node = node->right;
  157.       while (node->left != 0)
  158.         node = node->left;
  159.     }
  160.     else {
  161.       base_ptr y = node->parent;
  162.       while (node == y->right) {
  163.         node = y;
  164.         y = y->parent;
  165.       }
  166.       if (node->right != y)
  167.         node = y;
  168.     }
  169.   }
  170.  
  171.   void decrement()
  172.   {
  173.     __stl_verbose_assert(valid(), __STL_MSG_INVALID_ITERATOR); 
  174.     __stl_verbose_assert(node!=owner()->left, __STL_MSG_INVALID_ADVANCE); 
  175.     if (node->color == __rb_tree_red &&
  176.         node->parent->parent == node)
  177.       node = node->right;
  178.     else if (node->left != 0) {
  179.       base_ptr y = node->left;
  180.       while (y->right != 0)
  181.         y = y->right;
  182.       node = y;
  183.     }
  184.     else {
  185.       base_ptr y = node->parent;
  186.       while (node == y->left) {
  187.         node = y;
  188.         y = y->parent;
  189.       }
  190.       node = y;
  191.     }
  192.   }
  193. };
  194.  
  195. template <class Value>
  196. struct __rb_tree_iterator : public __rb_tree_base_iterator
  197. {
  198.   typedef Value& reference;
  199.   typedef const Value& const_reference;
  200.   typedef __rb_tree_node<Value>* link_type;
  201. private:
  202.   typedef __rb_tree_iterator<Value> self;
  203. public:
  204.   __rb_tree_iterator() {}
  205. # if defined ( __STL_DEBUG )
  206.   __rb_tree_iterator(const __safe_base* root, link_type x) : __rb_tree_base_iterator(root,x) {}
  207. # else
  208.   __rb_tree_iterator(link_type x) { node = x; }
  209. # endif
  210.   reference operator*() const { 
  211.       __stl_verbose_assert(node!=owner(), __STL_MSG_NOT_DEREFERENCEABLE); 
  212.       return link_type(node)->value_field; 
  213.   }
  214.  
  215.   self& operator++() { increment(); return *this; }
  216.   self operator++(int) {
  217.     self tmp = *this;
  218.     increment();
  219.     return tmp;
  220.   }
  221.     
  222.   self& operator--() { decrement(); return *this; }
  223.   self operator--(int) {
  224.     self tmp = *this;
  225.     decrement();
  226.     return tmp;
  227.   }
  228. };
  229.  
  230. template <class Value>
  231. struct __rb_tree_const_iterator : public __rb_tree_base_iterator
  232. {
  233.   typedef Value& reference;
  234.   typedef const Value& const_reference;
  235.   typedef __rb_tree_node<Value>* link_type;
  236. private:
  237.   typedef __rb_tree_const_iterator<Value> self;
  238. public:
  239.   __rb_tree_const_iterator() {}
  240. # if defined ( __STL_DEBUG )
  241.   __rb_tree_const_iterator(const __safe_base* root, link_type x) : 
  242.       __rb_tree_base_iterator(root,x) {}
  243.   __rb_tree_const_iterator(const __rb_tree_iterator<Value>& it) : 
  244.       __rb_tree_base_iterator((const __safe_base*)it.owner_,it.node) {
  245.   }
  246. # else
  247.   __rb_tree_const_iterator(link_type x) { node = x; }
  248.   __rb_tree_const_iterator(const __rb_tree_iterator<Value>& it) {
  249.       node = it.node;
  250.   }  
  251. # endif
  252.  
  253.   const_reference operator*() const { 
  254.       __stl_verbose_assert(node!=owner(), __STL_MSG_NOT_DEREFERENCEABLE); 
  255.       return link_type(node)->value_field; 
  256.   }
  257.  
  258.   self& operator++() { increment(); return *this; }
  259.   self operator++(int) {
  260.     self tmp = *this;
  261.     increment();
  262.     return tmp;
  263.   }
  264.     
  265.   self& operator--() { decrement(); return *this; }
  266.   self operator--(int) {
  267.     self tmp = *this;
  268.     decrement();
  269.     return tmp;
  270.   }
  271. };
  272.  
  273.  
  274. inline bool operator==(const __rb_tree_base_iterator& x,
  275.                        const __rb_tree_base_iterator& y) {
  276.   __stl_debug_check(__check_same_owner(x,y));                         
  277.   return x.node == y.node;
  278. }
  279.  
  280. //inline bool operator!=(const __rb_tree_base_iterator& x,
  281. //                       const __rb_tree_base_iterator& y) {
  282. //  return x.node != y.node;
  283. //}
  284.  
  285. inline bidirectional_iterator_tag 
  286. iterator_category(const __rb_tree_base_iterator&) {
  287.   return bidirectional_iterator_tag();
  288. }
  289.  
  290. inline __rb_tree_base_iterator::distance_type*
  291. distance_type(const __rb_tree_base_iterator&) {
  292.   return (__rb_tree_base_iterator::distance_type*) 0;
  293. }
  294.  
  295. template <class Value>
  296. inline Value* value_type(const __rb_tree_iterator<Value>&) {
  297.   return (Value*) 0;
  298. }
  299.  
  300. template <class Value>
  301. inline Value* value_type(const __rb_tree_const_iterator<Value>&) {
  302.   return (Value*) 0;
  303. }
  304.  
  305. inline void 
  306. __rb_tree_rotate_left(__rb_tree_node_base* x, __rb_tree_node_base*& root)
  307. {
  308.   __rb_tree_node_base* y = x->right;
  309.   x->right = y->left;
  310.   if (y->left != 0)
  311.     y->left->parent = x;
  312.   y->parent = x->parent;
  313.  
  314.   if (x == root)
  315.     root = y;
  316.   else if (x == x->parent->left)
  317.     x->parent->left = y;
  318.   else
  319.     x->parent->right = y;
  320.   y->left = x;
  321.   x->parent = y;
  322. }
  323.  
  324. inline void 
  325. __rb_tree_rotate_right(__rb_tree_node_base* x, __rb_tree_node_base*& root)
  326. {
  327.   __rb_tree_node_base* y = x->left;
  328.   x->left = y->right;
  329.   if (y->right != 0)
  330.     y->right->parent = x;
  331.   y->parent = x->parent;
  332.  
  333.   if (x == root)
  334.     root = y;
  335.   else if (x == x->parent->right)
  336.     x->parent->right = y;
  337.   else
  338.     x->parent->left = y;
  339.   y->right = x;
  340.   x->parent = y;
  341. }
  342.  
  343. inline void 
  344. __rb_tree_rebalance(__rb_tree_node_base* x, __rb_tree_node_base*& root)
  345. {
  346.   x->color = __rb_tree_red;
  347.   while (x != root && x->parent->color == __rb_tree_red) {
  348.     if (x->parent == x->parent->parent->left) {
  349.       __rb_tree_node_base* y = x->parent->parent->right;
  350.       if (y && y->color == __rb_tree_red) {
  351.         x->parent->color = __rb_tree_black;
  352.         y->color = __rb_tree_black;
  353.         x->parent->parent->color = __rb_tree_red;
  354.         x = x->parent->parent;
  355.       }
  356.       else {
  357.         if (x == x->parent->right) {
  358.           x = x->parent;
  359.           __rb_tree_rotate_left(x, root);
  360.         }
  361.         x->parent->color = __rb_tree_black;
  362.         x->parent->parent->color = __rb_tree_red;
  363.         __rb_tree_rotate_right(x->parent->parent, root);
  364.       }
  365.     }
  366.     else {
  367.       __rb_tree_node_base* y = x->parent->parent->left;
  368.       if (y && y->color == __rb_tree_red) {
  369.         x->parent->color = __rb_tree_black;
  370.         y->color = __rb_tree_black;
  371.         x->parent->parent->color = __rb_tree_red;
  372.         x = x->parent->parent;
  373.       }
  374.       else {
  375.         if (x == x->parent->left) {
  376.           x = x->parent;
  377.           __rb_tree_rotate_right(x, root);
  378.         }
  379.         x->parent->color = __rb_tree_black;
  380.         x->parent->parent->color = __rb_tree_red;
  381.         __rb_tree_rotate_left(x->parent->parent, root);
  382.       }
  383.     }
  384.   }
  385.   root->color = __rb_tree_black;
  386. }
  387.  
  388. inline __rb_tree_node_base*
  389. __rb_tree_rebalance_for_erase(__rb_tree_node_base* z,
  390.                               __rb_tree_node_base*& root,
  391.                               __rb_tree_node_base*& leftmost,
  392.                               __rb_tree_node_base*& rightmost)
  393. {
  394.   __rb_tree_node_base* y = z;
  395.   __rb_tree_node_base* x = 0;
  396.   __rb_tree_node_base* x_parent = 0;
  397.   if (y->left == 0)             // z has at most one non-null child. y == z.
  398.     x = y->right;               // x might be null.
  399.   else
  400.     if (y->right == 0)          // z has exactly one non-null child.  y == z.
  401.       x = y->left;              // x is not null.
  402.     else {                      // z has two non-null children.  Set y to
  403.       y = y->right;             //   z's successor.  x might be null.
  404.       while (y->left != 0)
  405.         y = y->left;
  406.       x = y->right;
  407.     }
  408.   if (y != z) {                 // relink y in place of z.  y is z's successor
  409.     z->left->parent = y; 
  410.     y->left = z->left;
  411.     if (y != z->right) {
  412.       x_parent = y->parent;
  413.       if (x) x->parent = y->parent;
  414.       y->parent->left = x;      // y must be a left child
  415.       y->right = z->right;
  416.       z->right->parent = y;
  417.     }
  418.     else
  419.       x_parent = y;  
  420.     if (root == z)
  421.       root = y;
  422.     else if (z->parent->left == z)
  423.       z->parent->left = y;
  424.     else 
  425.       z->parent->right = y;
  426.     y->parent = z->parent;
  427.     __STL_NAMESPACE::swap(y->color, z->color);
  428.     y = z;
  429.     // y now points to node to be actually deleted
  430.   }
  431.   else {                        // y == z
  432.     x_parent = y->parent;
  433.     if (x) x->parent = y->parent;   
  434.     if (root == z)
  435.       root = x;
  436.     else 
  437.       if (z->parent->left == z)
  438.         z->parent->left = x;
  439.       else
  440.         z->parent->right = x;
  441.     if (leftmost == z) 
  442.       if (z->right == 0)        // z->left must be null also
  443.         leftmost = z->parent;
  444.     // makes leftmost == header if z == root
  445.       else
  446.         leftmost = __rb_tree_node_base::minimum(x);
  447.     if (rightmost == z)  
  448.       if (z->left == 0)         // z->right must be null also
  449.         rightmost = z->parent;  
  450.     // makes rightmost == header if z == root
  451.       else                      // x == z->left
  452.         rightmost = __rb_tree_node_base::maximum(x);
  453.   }
  454.   if (y->color != __rb_tree_red) { 
  455.     while (x != root && (x == 0 || x->color == __rb_tree_black))
  456.       if (x == x_parent->left) {
  457.         __rb_tree_node_base* w = x_parent->right;
  458.         if (w->color == __rb_tree_red) {
  459.           w->color = __rb_tree_black;
  460.           x_parent->color = __rb_tree_red;
  461.           __rb_tree_rotate_left(x_parent, root);
  462.           w = x_parent->right;
  463.         }
  464.         if ((w->left == 0 || w->left->color == __rb_tree_black) &&
  465.             (w->right == 0 || w->right->color == __rb_tree_black)) {
  466.           w->color = __rb_tree_red;
  467.           x = x_parent;
  468.           x_parent = x_parent->parent;
  469.         } else {
  470.           if (w->right == 0 || w->right->color == __rb_tree_black) {
  471.             if (w->left) w->left->color = __rb_tree_black;
  472.             w->color = __rb_tree_red;
  473.             __rb_tree_rotate_right(w, root);
  474.             w = x_parent->right;
  475.           }
  476.           w->color = x_parent->color;
  477.           x_parent->color = __rb_tree_black;
  478.           if (w->right) w->right->color = __rb_tree_black;
  479.           __rb_tree_rotate_left(x_parent, root);
  480.           break;
  481.         }
  482.       } else {                  // same as above, with right <-> left.
  483.         __rb_tree_node_base* w = x_parent->left;
  484.         if (w->color == __rb_tree_red) {
  485.           w->color = __rb_tree_black;
  486.           x_parent->color = __rb_tree_red;
  487.           __rb_tree_rotate_right(x_parent, root);
  488.           w = x_parent->left;
  489.         }
  490.         if ((w->right == 0 || w->right->color == __rb_tree_black) &&
  491.             (w->left == 0 || w->left->color == __rb_tree_black)) {
  492.           w->color = __rb_tree_red;
  493.           x = x_parent;
  494.           x_parent = x_parent->parent;
  495.         } else {
  496.           if (w->left == 0 || w->left->color == __rb_tree_black) {
  497.             if (w->right) w->right->color = __rb_tree_black;
  498.             w->color = __rb_tree_red;
  499.             __rb_tree_rotate_left(w, root);
  500.             w = x_parent->left;
  501.           }
  502.           w->color = x_parent->color;
  503.           x_parent->color = __rb_tree_black;
  504.           if (w->left) w->left->color = __rb_tree_black;
  505.           __rb_tree_rotate_right(x_parent, root);
  506.           break;
  507.         }
  508.       }
  509.     if (x) x->color = __rb_tree_black;
  510.   }
  511.   return y;
  512. }
  513.  
  514. template <class Value, class Alloc>
  515. class __rb_tree_base {
  516.     typedef __rb_tree_base<Value,Alloc> self;
  517. public:
  518.     typedef Value value_type;
  519.     typedef value_type* pointer;
  520.     typedef const value_type* const_pointer;
  521.     typedef value_type& reference;
  522.     typedef const value_type& const_reference;
  523.     typedef size_t size_type;
  524.     typedef ptrdiff_t difference_type;
  525. protected:
  526.     typedef __rb_tree_node_base* base_ptr;
  527.     typedef __rb_tree_node<Value> rb_tree_node;
  528.     typedef __rb_tree_color_type color_type;
  529.     typedef rb_tree_node* link_type;
  530.     typedef simple_alloc<rb_tree_node, Alloc> rb_tree_node_allocator;
  531.     static link_type get_node() { return rb_tree_node_allocator::allocate(); }
  532.     static void put_node(link_type p) { rb_tree_node_allocator::deallocate(p); }
  533. protected:
  534.     link_type header;  
  535.  
  536.     link_type& root() const { return (link_type&) header->parent; }
  537.     link_type& leftmost() const { return (link_type&) header->left; }
  538.     link_type& rightmost() const { return (link_type&) header->right; }
  539.     size_type node_count; // keeps track of size of tree
  540.  
  541.     static link_type& left(link_type x) { return (link_type&)(x->left); }
  542.     static link_type& right(link_type x) { return (link_type&)(x->right); }
  543.     static link_type& parent(link_type x) { return (link_type&)(x->parent); }
  544.     static reference value(link_type x) { return x->value_field; }
  545.     static color_type& color(link_type x) { return (color_type&)(x->color); }
  546.  
  547.     static link_type& left(base_ptr x) { return (link_type&)(x->left); }
  548.     static link_type& right(base_ptr x) { return (link_type&)(x->right); }
  549.     static link_type& parent(base_ptr x) { return (link_type&)(x->parent); }
  550.     static reference value(base_ptr x) { return ((link_type)x)->value_field; }
  551.     static color_type& color(base_ptr x) { return (color_type&)(link_type(x)->color); }
  552.  
  553.     static link_type minimum(link_type x) { 
  554.         return (link_type)  __rb_tree_node_base::minimum(x);
  555.     }
  556.     static link_type maximum(link_type x) {
  557.         return (link_type) __rb_tree_node_base::maximum(x);
  558.     }
  559.  
  560. # if defined (__STL_DEBUG)
  561. protected:
  562.     friend class __safe_base;
  563.     mutable __safe_base iter_list;
  564. public:
  565.     void invalidate_all() {iter_list.invalidate_all();}
  566. # endif
  567.  
  568. public:    
  569.     __rb_tree_base() : header( get_node() ), node_count(0) {
  570.         color(header) = __rb_tree_red; // used to distinguish header from 
  571.         // root, in iterator.operator++
  572.         __stl_debug_do(iter_list.safe_init(header));
  573.     }
  574.     ~__rb_tree_base() {
  575.         put_node(header);
  576.         __stl_debug_do(iter_list.invalidate());
  577.     }
  578.  
  579. public:
  580.     bool empty() const { return node_count == 0; }
  581.     size_type size() const { return node_count; }
  582.     size_type max_size() const { return size_type(-1); }
  583.  
  584. protected:
  585.     static link_type __new_node(const value_type& v) {
  586.         link_type z = get_node();
  587.         __TRY {
  588.         construct(&(value(z)), v);
  589.         left(z) = 0;
  590.         right(z) = 0;
  591.         }
  592. #  if defined (__STL_USE_EXCEPTIONS)
  593.         catch(...) {
  594.             put_node(z);
  595.             throw;
  596.         }
  597. #  endif
  598.         return z;
  599.     }
  600.     static link_type __copy_aux(link_type x, link_type p);
  601.     static void __erase(link_type x);
  602.     static inline link_type __copy(link_type x, link_type p);
  603.  
  604. public:
  605.     void clear() {
  606.       if (node_count != 0) {
  607.         __erase(root());
  608.         leftmost() = header;
  609.         root() = 0;
  610.         rightmost() = header;
  611.         node_count = 0;
  612.         __stl_debug_do(invalidate_all());
  613.       }
  614.     }      
  615. };
  616.  
  617. template <class Key, class Value, class KeyOfValue, class Compare,
  618.           __DFL_TYPE_PARAM(Alloc,alloc) >
  619. class rb_tree : public __rb_tree_base<Value,Alloc> {
  620.     typedef __rb_tree_base<Value,Alloc> super;
  621.     typedef rb_tree<Key,Value,KeyOfValue,Compare,Alloc> self;
  622. public:
  623.     __IMPORT_CONTAINER_TYPEDEFS(super)
  624.     typedef __rb_tree_node_base* base_ptr;
  625.     typedef __rb_tree_node<Value> rb_tree_node;
  626.     typedef __rb_tree_color_type color_type;
  627.     typedef rb_tree_node* link_type;
  628.     typedef __rb_tree_iterator<value_type> iterator;
  629.     typedef __rb_tree_const_iterator<value_type> const_iterator;
  630.     typedef reverse_bidirectional_iterator<iterator, value_type, reference,
  631.                                            difference_type>
  632.         reverse_iterator; 
  633.     typedef reverse_bidirectional_iterator<const_iterator, value_type,
  634.                                            const_reference, difference_type>
  635.     const_reverse_iterator;
  636.     typedef Key key_type;
  637. protected:
  638.     Compare key_compare;
  639.     static const Key& key(link_type x) { return KeyOfValue()(value(x)); }
  640.     static const Key& key(base_ptr x) { return KeyOfValue()(value(link_type(x)));}
  641. private:
  642.     iterator __insert(base_ptr x, base_ptr y, const value_type& v);
  643.     void init() {
  644.         root() = 0;
  645.         leftmost() = header;
  646.         rightmost() = header;
  647.     }
  648. public:
  649.     // allocation/deallocation
  650.     rb_tree(): key_compare(Compare())  { init(); }
  651.     rb_tree(const Compare& comp): key_compare(comp)  { init(); }
  652.     rb_tree(const self& x) 
  653.       : key_compare(x.key_compare)  { 
  654.         root() = __copy(x.root(), header);
  655.         if (root() == 0) {
  656.             leftmost() = header;
  657.             rightmost() = header;
  658.         } else {
  659.         leftmost() = minimum(root());
  660.             rightmost() = maximum(root());
  661.         }
  662.         node_count = x.node_count;
  663.     }
  664.  
  665.     ~rb_tree() { clear();}
  666.     self& operator=(const self& x);
  667.     
  668. public:    
  669.     // accessors:
  670. # if defined (__STL_DEBUG)
  671.     iterator make_iterator(link_type l) { 
  672.         return iterator(&iter_list,l); 
  673.     }
  674.     const_iterator make_const_iterator(link_type l) const { 
  675.         return const_iterator(&iter_list,l); 
  676.     }
  677.     iterator begin() { return make_iterator(leftmost()); }
  678.     const_iterator begin() const { return make_const_iterator(leftmost()); }
  679.     iterator end() { return make_iterator(header); }
  680.     const_iterator end() const { return make_const_iterator(header); }
  681.     void invalidate_iterator(const iterator& it) { 
  682.         __invalidate_iterator(&iter_list,it.get_iterator(),it); 
  683.     }
  684. # else
  685.     iterator make_iterator(link_type l) { 
  686.         return iterator(l); 
  687.     }
  688.     const_iterator make_const_iterator(link_type l) const { 
  689.         return const_iterator(l); 
  690.     }
  691.     iterator begin() { return leftmost(); }
  692.     const_iterator begin() const { return leftmost(); }
  693.     iterator end() { return header; }
  694.     const_iterator end() const { return header; }
  695. # endif
  696.     reverse_iterator rbegin() { return reverse_iterator(end()); }
  697.     const_reverse_iterator rbegin() const { 
  698.         return const_reverse_iterator(end()); 
  699.     }
  700.     reverse_iterator rend() { return reverse_iterator(begin()); }
  701.     const_reverse_iterator rend() const { 
  702.         return const_reverse_iterator(begin());
  703.     } 
  704.     Compare key_comp() const { return key_compare; }
  705.  
  706.     void swap(self& t) {
  707.         __stl_debug_do(iter_list.swap_owners(t.iter_list));
  708.         __STL_NAMESPACE::swap(header, t.header);
  709.         __STL_NAMESPACE::swap(node_count, t.node_count);
  710.         __STL_NAMESPACE::swap(key_compare, t.key_compare);
  711.     }
  712.     
  713. public:
  714.     // insert/erase
  715.     pair<iterator,bool> insert_unique(const value_type& x);
  716.     iterator insert_equal(const value_type& x);
  717.  
  718.     iterator insert_unique(iterator position, const value_type& x);
  719.     iterator insert_equal(iterator position, const value_type& x);
  720.  
  721.     void insert_unique(const_iterator first, const_iterator last);
  722.     void insert_unique(const value_type* first, const value_type* last);
  723.     void insert_equal(const_iterator first, const_iterator last);
  724.     void insert_equal(const value_type* first, const value_type* last);
  725.  
  726.     void erase(iterator position);
  727.     void erase(iterator first, iterator last);
  728.     size_type erase(const key_type& x);
  729.     void erase(const key_type* first, const key_type* last);
  730.  
  731. public:
  732.                                 // set operations:
  733.     iterator find(const key_type& x);
  734.     const_iterator find(const key_type& x) const;
  735.     size_type count(const key_type& x) const;
  736.     iterator lower_bound(const key_type& x);
  737.     const_iterator lower_bound(const key_type& x) const;
  738.     iterator upper_bound(const key_type& x);
  739.     const_iterator upper_bound(const key_type& x) const;
  740.     pair<iterator,iterator> equal_range(const key_type& x);
  741.     pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
  742. public:
  743.                                 // Debugging.
  744.     bool __rb_verify() const;
  745. };
  746.  
  747. // fbp: these defines are for outline methods definitions.
  748. // needed for definitions to be portable. Should not be used in method bodies.
  749. # if defined  ( __STL_NESTED_TYPE_PARAM_BUG )
  750. #  define __iterator__        __rb_tree_iterator<Value>
  751. #  define __const_iterator__  __rb_tree_const_iterator<Value>
  752. #  define __size_type__       size_t
  753. #  define __link_type__       __rb_tree_node<Value>*
  754. #  define __base_ptr__        __rb_tree_node_base*
  755. #  define __value_type__      Value
  756. #  define __key_type__        Key
  757. # else
  758. #  define __iterator__        rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator
  759. #  define __const_iterator__  rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::const_iterator
  760. #  define __link_type__       rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::link_type
  761. #  define __size_type__       rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::size_type
  762. #  define __base_ptr__        rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::base_ptr
  763. #  define __value_type__      rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::value_type
  764. #  define __key_type__        rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::key_type
  765. # endif
  766.  
  767. template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
  768. inline bool operator==(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x, 
  769.                        const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& y) {
  770.     return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
  771. }
  772.  
  773. template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
  774. inline bool operator<(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x, 
  775.                       const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& y) {
  776.     return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
  777. }
  778.  
  779. template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
  780. rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& 
  781. rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::operator=
  782. (const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x) {
  783.     if (this != &x) {
  784.         // can't be done as in list because Key may be a constant type
  785.         clear();
  786.         root() = __copy(x.root(), header);
  787.         if (root() == 0) {
  788.             leftmost() = header;
  789.             rightmost() = header;
  790.         } else {
  791.         leftmost() = minimum(root());
  792.             rightmost() = maximum(root());
  793.         }
  794.         node_count = x.node_count;
  795.         key_compare = x.key_compare;
  796.     }
  797.     return *this;
  798. }
  799.  
  800.  
  801. template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
  802. __iterator__
  803. rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::__insert(__base_ptr__ x_, 
  804.                                                           __base_ptr__ y_, 
  805.                                                           const __value_type__& v) {
  806.     link_type x = (link_type) x_;
  807.     link_type y = (link_type) y_;
  808.     // determine link before allocating new node
  809.     bool link_to_left = y == header || x != 0 || key_compare(KeyOfValue()(v), key(y));
  810.     link_type z = __new_node(v);
  811.     if (link_to_left) {
  812.         left(y) = z;  // also makes leftmost() = z when y == header
  813.         if (y == header) {
  814.             root() = z;
  815.             rightmost() = z;
  816.         } else if (y == leftmost())
  817.             leftmost() = z;   // maintain leftmost() pointing to minimum node
  818.     } else {
  819.         right(y) = z;
  820.         if (y == rightmost())
  821.             rightmost() = z;   // maintain rightmost() pointing to maximum node
  822.     }
  823.     parent(z) = y;
  824.     left(z) = 0;
  825.     right(z) = 0;
  826.     __rb_tree_rebalance(z, header->parent);
  827.     ++node_count;
  828.     return make_iterator(z);
  829. }
  830.  
  831. template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
  832. __iterator__
  833. rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_equal(const __value_type__& v)
  834. {
  835.     link_type y = header;
  836.     link_type x = root();
  837.     while (x != 0) {
  838.         y = x;
  839.         x = key_compare(KeyOfValue()(v), key(x)) ? left(x) : right(x);
  840.     }
  841.     return __insert(x, y, v);
  842. }
  843.  
  844.  
  845. template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
  846. pair<__iterator__, bool>
  847. rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_unique(const __value_type__& v)
  848. {
  849.     link_type y = header;
  850.     link_type x = root();
  851.     bool comp = true;
  852.     while (x != 0) {
  853.         y = x;
  854.         comp = key_compare(KeyOfValue()(v), key(x));
  855.         x = comp ? left(x) : right(x);
  856.     }
  857.     iterator j = make_iterator(y);   
  858.     if (comp)
  859.         if (j == begin())     
  860.             return pair<iterator,bool>(__insert(x, y, v), true);
  861.         else
  862.             --j;
  863.     if (key_compare(key(j.node), KeyOfValue()(v)))
  864.         return pair<iterator,bool>(__insert(x, y, v), true);
  865.     return pair<iterator,bool>(j, false);
  866. }
  867.  
  868.  
  869. template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
  870. __iterator__ 
  871. rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_unique(
  872.     __iterator__ position, const __value_type__& v) {
  873.     __stl_debug_check(__check_if_owner(header,position));
  874.     if (position.node == header->left) // begin()
  875.         if (size() > 0 && key_compare(KeyOfValue()(v), key(position.node)))
  876.             return __insert(position.node, position.node, v);
  877.             // first argument just needs to be non-null 
  878.         else
  879.             return insert_unique(v).first;
  880.     else if (position.node == header) // end()
  881.         if (key_compare(key(rightmost()), KeyOfValue()(v)))
  882.             return __insert(0, rightmost(), v);
  883.         else
  884.             return insert_unique(v).first;
  885.     else {
  886.         iterator before = position;
  887.         --before;
  888.         if (key_compare(key(before.node), KeyOfValue()(v))
  889.             && key_compare(KeyOfValue()(v), key(position.node)))
  890.             if (right(before.node) == 0)
  891.                 return __insert(0, before.node, v); 
  892.             else
  893.                 return __insert(position.node, position.node, v);
  894.                 // first argument just needs to be non-null 
  895.         else
  896.             return insert_unique(v).first;
  897.     }
  898. }
  899.  
  900. template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
  901. __iterator__ 
  902. rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_equal(
  903.     __iterator__ position, const __value_type__& v) {
  904.     __stl_debug_check(__check_if_owner(header,position));
  905.     if (position.node == header->left) // begin()
  906.         if (size() > 0 && key_compare(KeyOfValue()(v), key(position.node)))
  907.             return __insert(position.node, position.node, v);
  908.             // first argument just needs to be non-null 
  909.         else
  910.             return insert_equal(v);
  911.     else if (position.node == header) // end()
  912.         if (!key_compare(KeyOfValue()(v), key(rightmost())))
  913.             return __insert(0, rightmost(), v);
  914.         else
  915.             return insert_equal(v);
  916.     else {
  917.         iterator before = position;
  918.         --before;
  919.         if (!key_compare(KeyOfValue()(v), key(before.node))
  920.             && !key_compare(key(position.node), KeyOfValue()(v)))
  921.             if (right(before.node) == 0)
  922.                 return __insert(0, before.node, v); 
  923.             else
  924.                 return __insert(position.node, position.node, v);
  925.                 // first argument just needs to be non-null 
  926.         else
  927.             return insert_equal(v);
  928.     }
  929. }
  930.  
  931. template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
  932. void
  933. rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_equal(const __value_type__* first, 
  934.                                                               const __value_type__* last) {
  935.     while (first != last) insert_equal(*first++);
  936. }
  937.  
  938. template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
  939. void
  940. rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_equal(__const_iterator__ first,
  941.                         __const_iterator__ last) {
  942.     while (first != last) insert_equal(*first++);
  943. }
  944.  
  945. template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
  946. void 
  947. rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_unique(const __value_type__* first, 
  948.                                                                const __value_type__* last) {
  949.     while (first != last) insert_unique(*first++);
  950. }
  951.  
  952. template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
  953. void 
  954. rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_unique(__const_iterator__ first,
  955.                                                                __const_iterator__ last) {
  956.     while (first != last) insert_unique(*first++);
  957. }
  958.          
  959. template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
  960. inline void
  961. rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::erase(__iterator__ 
  962.                                                        position) {
  963.     __stl_debug_check(__check_if_owner(header,position));
  964.     __stl_verbose_assert(position.node!=header, __STL_MSG_ERASE_PAST_THE_END);
  965.     __stl_debug_do(invalidate_iterator(position));
  966.   link_type y = (link_type) __rb_tree_rebalance_for_erase(position.node,
  967.                                                           header->parent,
  968.                                                           header->left,
  969.                                                           header->right);
  970.   destroy(&(value(y)));
  971.   put_node(y);
  972.   --node_count;
  973. }
  974.  
  975. template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
  976. __size_type__
  977. rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::erase(const __key_type__& x) {
  978.     pair<iterator,iterator> p = equal_range(x);
  979.     size_type n = 0;
  980.     distance(p.first, p.second, n);
  981.     erase(p.first, p.second);
  982.     return n;
  983. }
  984.  
  985. template <class Value, class Alloc>
  986. inline __rb_tree_node<Value>*
  987. __rb_tree_base<Value, Alloc>::__copy(__rb_tree_node<Value>* x, __rb_tree_node<Value>* p) {
  988.     link_type l;
  989. #  if defined (__STL_USE_EXCEPTIONS)
  990.     l = left(p);
  991. #  endif
  992.     __TRY {
  993.     l = __copy_aux(x, p);
  994.     }
  995. #  if defined (__STL_USE_EXCEPTIONS)
  996.     catch(...) {
  997.         if (left(p) != l) {
  998.             __erase(left(p));
  999.             left(p) = l;
  1000.         }
  1001.         throw;
  1002.     }
  1003. #  endif
  1004.     return l;
  1005. }
  1006.  
  1007. template <class Value, class Alloc>
  1008. __rb_tree_node<Value>*
  1009. __rb_tree_base<Value, Alloc>::__copy_aux(__rb_tree_node<Value>* x, 
  1010.                                          __rb_tree_node<Value>* p) {
  1011.    // structural copy
  1012.    link_type r = x;
  1013.    while (x != 0) {
  1014.       link_type y = __new_node(value(x));
  1015.       if (r == x) r = y;  // save for return value
  1016.       left(p) = y;
  1017.       parent(y) = p;
  1018.       color(y) = color(x);
  1019.       right(y) = __copy_aux(right(x), y);
  1020.       left(y) = 0;
  1021.       p = y;
  1022.       x = left(x);
  1023.    }
  1024.    left(p) = 0;
  1025.    return r;
  1026. }
  1027.  
  1028.  
  1029. template <class Value, class Alloc>
  1030. void __rb_tree_base<Value, Alloc>::__erase(__rb_tree_node<Value>* x) {
  1031.     // erase without rebalancing
  1032.     while (x != 0) {
  1033.        __erase(right(x));
  1034.        link_type y = left(x);
  1035.        destroy(&(value(x)));
  1036.        put_node(x);
  1037.        x = y;
  1038.     }
  1039. }
  1040.  
  1041. template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
  1042. void
  1043. rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::erase(__iterator__ first, 
  1044.                                                        __iterator__ last) {
  1045.     if (first == begin() && last == end())
  1046.         clear();
  1047.     else
  1048.          while (first != last) erase(first++);
  1049. }
  1050.  
  1051. template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
  1052. void rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::erase(const Key* first, 
  1053.                       const Key* last) {
  1054.     while (first != last) erase(*first++);
  1055. }
  1056.  
  1057. template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
  1058. __iterator__
  1059. rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::find(const __key_type__& k) {
  1060.    link_type y = header; /* Last node which is not less than k. */
  1061.    link_type x = root(); /* Current node. */
  1062.  
  1063.    while (x != 0) 
  1064.      if (!key_compare(key(x), k))
  1065.        y = x, x = left(x);
  1066.    else
  1067.        x = right(x);
  1068.  
  1069.    return make_iterator((y == header || key_compare(k, key(y))) ? header : y);
  1070. }
  1071.  
  1072. template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
  1073. __const_iterator__
  1074. rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::find(const __key_type__& k) const {
  1075.    link_type y = header; /* Last node which is not less than k. */
  1076.    link_type x = root(); /* Current node. */
  1077.  
  1078.    while (x != 0) {
  1079.      if (!key_compare(key(x), k))
  1080.        y = x, x = left(x);
  1081.    else
  1082.        x = right(x);
  1083.    }
  1084.    return make_const_iterator((y == header || key_compare(k, key(y))) ? header : y);
  1085. }
  1086.  
  1087. template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
  1088. __size_type__
  1089. rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::count(const __key_type__& k) const {
  1090.     pair<const_iterator, const_iterator> p = equal_range(k);
  1091.     size_type n = 0;
  1092.     distance(p.first, p.second, n);
  1093.     return n;
  1094. }
  1095.  
  1096. template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
  1097. __iterator__
  1098. rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::lower_bound(const __key_type__& k) {
  1099.    link_type y = header; /* Last node which is not less than k. */
  1100.    link_type x = root(); /* Current node. */
  1101.  
  1102.    while (x != 0) 
  1103.      if (!key_compare(key(x), k))
  1104.        y = x, x = left(x);
  1105.      else
  1106.        x = right(x);
  1107.  
  1108.    return make_iterator(y);
  1109. }
  1110.  
  1111. template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
  1112. __const_iterator__
  1113. rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::lower_bound(const __key_type__& k) const {
  1114.    link_type y = header; /* Last node which is not less than k. */
  1115.    link_type x = root(); /* Current node. */
  1116.  
  1117.    while (x != 0) 
  1118.      if (!key_compare(key(x), k))
  1119.        y = x, x = left(x);
  1120.      else
  1121.        x = right(x);
  1122.  
  1123.    return make_const_iterator(y);
  1124. }
  1125.  
  1126. template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
  1127. __iterator__
  1128. rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::upper_bound(const __key_type__& k) {
  1129.   link_type y = header; /* Last node which is greater than k. */
  1130.   link_type x = root(); /* Current node. */
  1131.  
  1132.    while (x != 0) 
  1133.      if (key_compare(k, key(x)))
  1134.        y = x, x = left(x);
  1135.      else
  1136.        x = right(x);
  1137.  
  1138.    return make_iterator(y);
  1139. }
  1140.  
  1141. template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
  1142. __const_iterator__
  1143. rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::upper_bound(const __key_type__& k) const {
  1144.   link_type y = header; /* Last node which is greater than k. */
  1145.   link_type x = root(); /* Current node. */
  1146.  
  1147.    while (x != 0) 
  1148.      if (key_compare(k, key(x)))
  1149.        y = x, x = left(x);
  1150.      else
  1151.        x = right(x);
  1152.  
  1153.    return make_const_iterator(y);
  1154. }
  1155.  
  1156. template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
  1157. inline pair<__iterator__,__iterator__>
  1158. rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::equal_range(const __key_type__& k) {
  1159.     return pair<iterator, iterator>(lower_bound(k), upper_bound(k));
  1160. }
  1161.  
  1162. template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
  1163. inline pair<__const_iterator__,__const_iterator__>
  1164. rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::equal_range(const __key_type__& k) const {
  1165.     return pair<const_iterator,const_iterator>(lower_bound(k), upper_bound(k));
  1166. }
  1167.  
  1168. inline int __black_count(__rb_tree_node_base* node, __rb_tree_node_base* root)
  1169. {
  1170.   if (node == 0)
  1171.     return 0;
  1172.   else {
  1173.     int bc = node->color == __rb_tree_black ? 1 : 0;
  1174.     if (node == root)
  1175.       return bc;
  1176.     else
  1177.       return bc + __black_count(node->parent, root);
  1178.   }
  1179. }
  1180.  
  1181. template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
  1182. bool 
  1183. rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::__rb_verify() const
  1184. {
  1185.   int len = __black_count(leftmost(), root());
  1186.   for (const_iterator it = begin(); it != end(); ++it) {
  1187.     link_type x = (link_type) it.node;
  1188.     link_type L = left(x);
  1189.     link_type R = right(x);
  1190.  
  1191.     if (x->color == __rb_tree_red)
  1192.       if ((L && L->color == __rb_tree_red) ||
  1193.           (R && R->color == __rb_tree_red))
  1194.         return false;
  1195.  
  1196.     if (L && key_compare(key(x), key(L)))
  1197.       return false;
  1198.     if (R && key_compare(key(R), key(x)))
  1199.       return false;
  1200.  
  1201.     if (!L && !R && __black_count(x, root()) != len)
  1202.       return false;
  1203.   }
  1204.  
  1205.   if ( !empty() )
  1206.   {
  1207.       if (leftmost() != __rb_tree_node_base::minimum(root()))
  1208.         return false;
  1209.       if (rightmost() != __rb_tree_node_base::maximum(root()))
  1210.         return false;
  1211.   }
  1212.   
  1213.   return true;
  1214. }
  1215.  
  1216. # undef __iterator__        
  1217. # undef __const_iterator__  
  1218. # undef __size_type__  
  1219. # undef __link_type__  
  1220. # undef __base_ptr__        
  1221. # undef __value_type__
  1222. # undef __key_type__  
  1223.  
  1224. __END_STL_NAMESPACE
  1225.  
  1226. #endif
  1227.  
  1228.